package BucketMapping;

// BucketMapping.java

import java.util.*;

public class BucketMapping {
	static final double LOAD = 0.5;     // default load factor
	static final MappingRecord DELETED = new MappingRecord("");     // sentinels for deleted
	
	private MappingRecord[] table;
	private int capacity;
	private int size;
	
	public BucketMapping(int capacity){
		this.capacity = capacity;
		int length = (int)Math.pow(2, Math.ceil(Math.log(capacity/LOAD)/Math.log(2)));
		table = new MappingRecord[length];
		size = 0;
	}
	
	//gets an iterator of the key
	public Iterator get(String key){
		int loc = findLocation(key);
		if(loc==-1)
			return null;
		else
			return table[loc].getIterator();
	}
	
	public int size(){
		return size;
	}
	
	//removes a object
	public void remove(String key){
		int loc = findLocation(key);
		if(loc!=-1){
			
			table[loc]=DELETED;
			size--;
		}
	}
	
	//inserts an object
	public void put(String key, Object data){
		
		int loc = findLocation(key);
		try{
			if(table[loc].getKey()==hashCode(key))
				table[loc].addItem(data);
		}catch(ArrayIndexOutOfBoundsException aioobe){
			loc = findInsertLocation(key);
			try{
				if(table[loc]==DELETED)
					table[loc] = table[loc]= new MappingRecord(hashCode(key), data);
				else
					table[loc].addItem(data);
			}catch(NullPointerException npe2){
				table[loc]= new MappingRecord(hashCode(key), data);
			}
		}
		//Terminal.println("Put "+loc);
		size++;
		
	}
		//determines if the key is contained
	public boolean containsKey(String key){
		if(findLocation(key)==-1)			
			return false;
		else
			return true;
	}
	
	private int findLocation(String key){
		return findLocation(hashCode(key));
	}
	
	//finds a location from the hashcode, finds the hashcode or null
	private int findLocation(int code){
		int start = hash(code);
		try{
			if(table[start].getKey()==code){
				echoProbe(start);
				return start;
			}
				
			else{
				int loc = start;
				int i=0;		//to make sure if array is full to not get stuck in an endless loop
				int step = stepHash(code);
				while(table[loc]!=null 
						&& table[loc].getKey() != code
						&& i<table.length){
					loc = (loc+step)%table.length;
					i++;
					echoProbe(loc);
				}
				if(table[loc].getKey() == code)
					return loc;
				else 
					return -1;
			}	
		}catch(NullPointerException npe){
			return -1;
		}
	}
	
	//finds the location to insert a value into, selects first deleted, null, or same key location
	private int findInsertLocation(String key){
		int code = hashCode(key);
		int start = hash(code);
		try{
			echoProbe(start);
			table[start].getKey();
		}catch(NullPointerException npe){
			return start;//occurs when value is null or deleted item is at location
		}
		int loc = start;
		int i=0;		//to make sure if array is full to not get stuck in an endless loop
		int step = stepHash(code);
		while(table[loc]!=null 
				&& table[loc] != DELETED
				&& table[loc].getKey() != code
				&& i<table.length){
			loc = (loc+step)%table.length;
			i++;
			echoProbe(loc);
		}
		if(i<table.length)
			return loc;
		else 
			return -1;
	}
	
	private static void echoProbe(int loc){
		//Terminal.println("Probing "+loc);
	}
	
	// Converts a string into an integer to use for the hash functions.
	// This function is based upon a linear-congruential pesudorandom number
	// generator, in which successive values r_i are  generated by computing
	//    r_i = ( A * r_(i-1) + B ) mod M
	// A is a large prime number, while B is a small increment used to
	// ensure we don't just compute successive powers of A mod M.
	//
	// The above generator is modified to add thee ith character of the
	// string and its offset, to alter the pseudorandom sequence.

	int hashCode(String s){
		int A = 1952786893;
		int B = 367253;
		int v = B;
	
		for (int j = 0; j < s.length(); j++){
		    char c = s.charAt(j);
		    v = A * (v + (int)c + j) + B;
		}
		if (v < 0) 
			v = -v;  //return a positive integer
		return v;
	}

	// Primary hash function using the multiplication method
	//   Computes hashKey*a - floor(k*a) and keeps most two significant digits
	//   of the resulting fraction to return 
	//
	// The below assumes that the hash table is called table

	public int hash(int hashKey){
		double a = (Math.sqrt(5.0)-1)/2;
		double frac = (hashKey * a) - (int)(hashKey * a);
		int hashValue = (int) (table.length * frac);
		return hashValue;                                
	}
    
	// 
	// Secondary hash function which is guaranteed to be odd.  To ensure that all
	// table entries are visited, this requrires that tableSize is a power of 2. 

	public int stepHash(int hashKey){
		int step = (hashKey % (table.length/2 - 1));
		return 2*step + 1;
	}

}
